#include "myTree.h"

using namespace std;

// 创建头节点，并初始化为线索二叉树
TreeNode* Thrt = new TreeNode('#', NULL, NULL, Link, Thread); // 设置头节点

// 树节点的构造函数
TreeNode::TreeNode(char d, TreeNode* ld, TreeNode* rd, NodeTag lt, NodeTag rt) {
    this->data = d;           // 节点数据赋值
    this->leftChild = ld;    // 左子节点
    this->rightChild = rd;   // 右子节点
    this->lTag = lt;         // 左标志
    this->rTag = rt;         // 右标志
}

TreeNode::~TreeNode() {
    // 析构函数
}

// MyTree类的构造与析构函数

// 无参构造函数，初始化根节点为空，线程标志为false
MyTree::MyTree() {
    this->root = NULL;      
    this->isThread = false; 
}

// 接收字符数组构造树的构造函数
MyTree::MyTree(const char c[]) {
    int i = 0;                              
    this->root = createTree(c, &i);       
    this->isThread = false;                
}

// 创建树的函数，使用字符数组
TreeNode* MyTree::createTree(const char str[], int* i) {
    if (str[*i] == '\0' || str[*i] == '@') {
        return NULL; 
    } else {
        TreeNode* p = new TreeNode(str[*i], NULL, NULL, Link, Link); 
        ++(*i); 
        p->leftChild = createTree(str, i); 
        ++(*i); 
        p->rightChild = createTree(str, i); 
        return p; 
    }
}

// 拷贝构造函数
MyTree::MyTree(const MyTree& t) {
    this->root = copyTree(t.root);          
    this->isThread = t.isThread;           
}

// 复制树的函数
TreeNode* MyTree::copyTree(TreeNode* node) {
    if (!node) {
        return NULL; 
    }
    TreeNode* newNode = new TreeNode(node->data, NULL, NULL, Link, Link); 
    if (node->leftChild) {
        newNode->leftChild = copyTree(node->leftChild); 
        
    } else {
        newNode->leftChild = NULL; 
    }
    if (node->rightChild) {
        newNode->rightChild = copyTree(node->rightChild); 
    } else {
        newNode->rightChild = NULL; 
    }
    return newNode; 
}

// 析构函数，删除树并置空根节点
MyTree::~MyTree() {
    DeleteTree(this->root); 
    this->root = NULL;      
}

// 删除树的函数
void MyTree::DeleteTree(TreeNode* node) {
    if (node == NULL) {
        return; 
    }
    if (node->lTag == Link) DeleteTree(node->leftChild); 
    if (node->rTag == Link) DeleteTree(node->rightChild); 
    delete node; 
}

// 前序遍历树的函数
void MyTree::preOrderTraverse() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) { 
        preOrder(tmp);            
    }
}
// 前序遍历的实现
void MyTree::preOrder(TreeNode* node) {
    if (node) {
        node->printNode();
        preOrder(node->leftChild); 
        preOrder(node->rightChild); 
    }
}

// 中序遍历树的函数
void MyTree::inOrderTraverse() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) { 
        inOrder(tmp);           
    } else {
        inOrderTraverse_Thr(Thrt);
    }
}

// 中序遍历的实现（非线索二叉树）
void MyTree::inOrder(TreeNode* node) {
    if (node) {
        inOrder(node->leftChild); 
        node->printNode();        
        inOrder(node->rightChild); 
    }
}

// 中序遍历的实现（线索二叉树）
void MyTree::inOrderTraverse_Thr(TreeNode* node) {
    TreeNode* temp = node->leftChild; 
    while (temp != node) { 
        while (temp->lTag == Link) { 
            temp = temp->leftChild; 
        }
        temp->printNode();
        while (temp->rTag == Thread && temp->rightChild != node) { 
            temp = temp->rightChild; 
            temp->printNode();
        }
        temp = temp->rightChild;
    }
}

// 后序遍历树的函数
void MyTree::postOrderTraverse() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) {
        postOrder(tmp);          
    }
}

// 后序遍历的实现
void MyTree::postOrder(TreeNode* node) {
    if (node) {
        postOrder(node->leftChild); 
        postOrder(node->rightChild); 
        node->printNode();           
    }
}

// 统计叶节点数量
int MyTree::countLeaf() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) { 
        return leafNum(tmp);      
    }
    return 0; 
}

// 统计叶节点数量的实现
int MyTree::leafNum(TreeNode* node) {
    if (!node) {
        return 0; 
    } else if(!node->leftChild && !node->rightChild) {
        return 1; 
    } else {
        return leafNum(node->leftChild) + leafNum(node->rightChild); 
    }
}

// 计算树的高度
int MyTree::countHeight() {
    TreeNode* tmp = this->root; 
    if (this->isThread == false) { 
        return treeHeight(tmp);    
    }
    return 0; 
}

// 计算树的高度的实现
int MyTree::treeHeight(TreeNode* node) {
    if (!node) {
        return 0; 
    } else {
        int m = treeHeight(node->leftChild); 
        int n = treeHeight(node->rightChild); 
        return (m > n) ? m + 1 : n + 1; 
    }
}

// 判断是否为线索二叉树
bool MyTree::isThreadedTree() {
    return this->isThread; 
}

// 中序线索化函数
TreeNode* pre = NULL; 
bool MyTree::inOrderThreading() {
    this->isThread = true; 
    Thrt->rightChild = Thrt; 
    if (!this->root) { 
        Thrt->leftChild = Thrt; 
    } else {
        Thrt->leftChild = this->root; 
        pre = Thrt;
        inThreading(this->root);
        pre->rTag = Thread;
        pre->rightChild = Thrt; 
        Thrt->rightChild = pre;
    }
    return this->isThread; 
}

// 进行二叉树的中序线索化
void MyTree::inThreading(TreeNode* node) {
    if (node != NULL) { 
        inThreading(node->leftChild); 
        if (node->leftChild == NULL) {
            node->lTag = Thread; 
            node->leftChild = pre; 
        }
        if (pre->rightChild == NULL) {
            pre->rTag = Thread; 
            pre->rightChild = node; 
        }
        pre = node;
        inThreading(node->rightChild);
    }
}

// 结点定位函数，查找指定数据的节点
TreeNode& MyTree::locateNode(const char& d) {
    TreeNode* tmp = this->root; 
    return *locate(tmp, d); 
}

// 定位指定字符的节点
TreeNode* MyTree::locate(TreeNode* node, const char& c) {
    if (node->data == c) { 
        return node; 
    }
    if (node->leftChild && node->lTag != Thread) { 
        TreeNode* p = locate(node->leftChild, c); 
        if (p) {
            return p; 
        }
    }
    if (node->rightChild && node->rTag != Thread) { 
        TreeNode* p = locate(node->rightChild, c); 
        if (p) {
            return p; 
        }
    }
    return NULL; 
}

// 获取线索二叉树当前节点的前驱节点
TreeNode& MyTree::preNode(const TreeNode& node) {
    TreeNode* p = node.leftChild; 
    if (this->isThread == false) { 
        this->inOrderThreading(); 
    }
    if (node.lTag == Thread) {
        return *(node.leftChild); 
    } else {
        return *(inOrderLastNode(p)); 
    }
}

// 获取线索二叉树当前节点的后继节点
TreeNode& MyTree::nextNode(const TreeNode& node) {
    TreeNode* p = node.rightChild; 
    if (this->isThread == false) {
        this->inOrderThreading(); 
    }
    if (node.rTag == Thread) { 
        return *(node.rightChild); 
    } else {
        return *(inOrderFirstNode(p));
    }
}

// 获取中序下当前节点右子树的最后一个节点
TreeNode* MyTree::inOrderLastNode(TreeNode* node) {
    TreeNode* tmp = node; 
    while (tmp->rTag == Link) { 
        tmp = tmp->rightChild; 
    }
    return tmp; 
}

// 获取中序下当前节点左子树的第一个节点
TreeNode* MyTree::inOrderFirstNode(TreeNode* node) {
    TreeNode* tmp = node; 
    while (tmp->lTag == Link) {
        tmp = tmp->leftChild; 
    }
    return tmp; 
}

void TreeNode::printNode()
{
    cout << this->data;
}

HuffmanNode::HuffmanNode(int v, int f) : value(v), freq(f), left(nullptr), right(nullptr) {}

bool Compare::operator()(HuffmanNode* a, HuffmanNode* b) {
    return a->freq > b->freq;
}

HuffmanTree::HuffmanTree(const int& n, const int vals[]) {
   
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    
   
    for (int i = 0; i < n; i++) {
        pq.push(new HuffmanNode(vals[i], vals[i])); 
    }
    
    // 构建哈夫曼树
    while (pq.size() > 1) { 
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop(); 
        // 创建一个新的节点，其频率为两个子节点的频率之和
        HuffmanNode* combined = new HuffmanNode(0, left->freq + right->freq);
        combined->left = left;
        combined->right = right; 
        pq.push(combined); 
    }
    
    root = pq.top(); 
}

HuffmanTree::~HuffmanTree() {
    // 析构函数，用于释放哈夫曼树节点
    // TBD: 实现树的删除，如果需要的话
}

void HuffmanTree::generateCodes(HuffmanNode* node, string code, map<int, string>& codes) {
    if (!node) return; 
    if (!node->left && !node->right) {
        codes[node->value] = code; 
    }
    generateCodes(node->left, code + "0", codes); 
    generateCodes(node->right, code + "1", codes); 
}

void HuffmanTree::printHuffmanCodes() {
    map<int, string> codes;
    generateCodes(root, "", codes);
    
    
    vector<pair<int, string>> sortedCodes(codes.begin(), codes.end());
    
    
    sort(sortedCodes.begin(), sortedCodes.end(), [](const pair<int, string>& a, const pair<int, string>& b) {
        return a.first > b.first; 
    });
    
   
    for (const auto& pair : sortedCodes) {
        cout << pair.first << ":" << pair.second << endl;
    }
}